/**
 * 归并排序
 */
public class MergeSort {
  public static void main(String[] args) {
    int[] array = new int[]{3, 5, 1, 2, 4, 8, 0};
    // 调用归并排序
    mergeSort(array, 0, array.length - 1);
    for (int arr : array) {
      System.out.println(arr);
    }
  }

  public static void mergeSort(int[] arr, int left, int right) {
    if (right <= left) {
      return;
    }
    // (left + right) >> 1等效为(left + right) / 2
    int mid = (left + right) >> 1;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
  }

  private static void merge(int[] arr, int left, int mid, int right) {
    int[] tmp = new int[right - left + 1];
    int i = left, j = mid + 1, k = 0;
    // 取出左半边和右半边中的较小值放入tmp数组
    while (i <= mid && j <= right) {
      tmp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
    }
    // 若i <= mid，则说明左半边的数据没有放完，再依次放入tmp即可
    while (i <= mid) {
      tmp[k++] = arr[i++];
    }
    // 若j <= right，则说明右半边的数据没有放完，再依次放入tmp即可
    while (j <= right) {
      tmp[k++] = arr[j++];
    }
    // 将合并后的数组再拷贝回原数组
    for (int p = 0; p < tmp.length; p++) {
      arr[left + p] = tmp[p];
    }
    // 也可以写作：System.arraycopy(tmp, 0, arr, left, tmp.length);
    /**
     * src      the source array.
     * srcPos   starting position in the source array.
     * dest     the destination array.
     * destPos  starting position in the destination data.
     * length   the number of array elements to be copied.
     */
  }
}
